9E - Interestring graph and Apples - CodeForces Solution

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define double long double
#define endl "\n"
#define input(a) for(auto &x:a) cin>>x
#define all(x) x.begin(),x.end()
#define rsort(c) sort(all(c)); reverse(all(c))
#define sz(c) (int)c.size()
#define print(a) for(auto x : a) cout << x << " "; cout << endl
#define print1(a) for(auto x : a) cout << x.first << " " << x.second << endl
#define printall(a) for(auto x:a){ print(x); } cout<<endl
#define fil(ar, val) memset(ar, val, sizeof(ar))  // 0x3f for inf, 0x80 for -INF can also use with pairs

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pi;
typedef vector<pair<int,int>> vpi;

template<typename T> using PQ = priority_queue<T>;
template<typename T> using QP = priority_queue<T,vector<T>,greater<T>>;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>T min(const vector<T>&v){return *min_element(v.begin(),v.end());}
template<typename T>T max(const vector<T>&v){return *max_element(v.begin(),v.end());}
template<typename T>T acc(const vector<T>&v){return accumulate(v.begin(),v.end(),T(0));};

#ifndef ONLINE_JUDGE
#include<debug.h>
#else
#define bug(...)
#define bug1(...)
#define debug(x)
#endif

// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
// cout<<rng()%100<<endl;

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);   
}
int digitsum(int n){int ret=0;while(n){ret+=n%10;n/=10;}return ret;}
int power(int x,int n){
    if(n==0)    return 1;
    int a=power(x,n/2);
    if(n%2==0)  return (a*a);
    else    return (a*a*x);
}
void myerase(ordered_set<int> &s, int v){
    int rank = s.order_of_key(v);
    auto it = s.find_by_order(rank);
    s.erase(it);
}
void myerase(ordered_multiset<int> &s, int v){
    int rank = s.order_of_key(v);
    auto it = s.find_by_order(rank);
    s.erase(it);
}
int lsbit(int n){
    int res=((n) & -(n));
    return __builtin_ctz(res);
}
int isPerfectSquare(int x) {
    int s = (int) sqrtl(x);
    while (s * s < x) s++;
    while (s * s > x) s--;
    return s*s==x;
}

struct DSU {
    vector<int> e;
    DSU(int N) { e = vector<int>(N, -1); }

    // get representive component (uses path compression)
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

    bool same_set(int a, int b) { return get(a) == get(b); }

    int size(int x) { return -e[get(x)]; }

    bool unite(int x, int y) {  // union by size
        x = get(x), y = get(y);
        if (x == y) return false;
        // if (e[x] > e[y]) swap(x, y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
};
// DSU d(n+1);
//DECLARE DP GLOBALLY;
//THINK BEFORE USING SET/MULTISET;
void solve(){
    int n,m;
    cin>>n>>m;
    vi deg(n+1);
    DSU d(n+1);
    bool exist_cycle=0;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        deg[u]++;
        deg[v]++;
        exist_cycle|=d.same_set(u,v);
        d.unite(u,v);
    }
    // check if the graph is already interesting;
    bool check1=1;
    for(int i=1;i<=n;i++){
        if(deg[i]!=2){
            check1=0;
        }
    }
    for(int i=2;i<=n;i++){
        if(!d.same_set(i,1)){
            check1=0;
        }
    }
    if(check1){
        cout<<"YES"<<endl;
        cout<<0<<endl;
        return;
    }
    // check if the graph cannot be made interesting;
    bool check2=0;
    if(m>=n){
        check2=1;
    }
    for(int i=1;i<=n;i++){
        if(deg[i]>2){
            check2=1;
        }
    }
    if(exist_cycle){
        check2=1;
    }
    if(check2){
        cout<<"NO"<<endl;
        return;
    }
    cout<<"YES"<<endl;
    cout<<n-m<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(deg[i]<2 && deg[j]<2 && (!d.same_set(i,j))){
                cout<<i<<" "<<j<<endl;
                deg[i]++;
                deg[j]++;
                d.unite(i,j);
            }
        }
    }
    bug(n);
    int u,v;
    for(int i=1;i<=n;i++){
        if(deg[i]<2){
            u=i;
            break;
        }
    }
    for(int j=n;j>=1;j--){
        if(deg[j]<2){
            v=j;
            break;
        }
    }
    cout<<u<<" "<<v<<endl;
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    // int tt=1;
    int t=1;
    // cin>>t;
    while(t--){
        // cout<<"Case #"<<tt<<": ";
        // tt++;
        solve();
    }
    return 0;
}